package algocasts;

public class P148_MaximalSquare {
    private int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }

    // Time: O(m*n)  Space: O(m*n)
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0
                || matrix[0] == null || matrix[0].length == 0)
            return 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] d = new int[m][n];
        int len = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0 || matrix[i][j] == '0')
                    d[i][j] = matrix[i][j] == '1' ? 1 : 0;
                else
                    d[i][j] = min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]) + 1;
                len = Math.max(len, d[i][j]);
            }
        }
        return len * len;
    }
}
